|
Evolution of a random network is a dynamical process, usually leading to emergence of giant component accompanied with striking consequences on the network topology. To quantify this process, there is a need of inspection on how the size of the largest connected cluster within the network, .〔Albert-László Barabási. Network Science: Chapter 3〕 Networks change their topology as they evolve, undergoing phase transitions. Phase transitions are generally known from physics, where it occurs as matter changes state according to its thermal energy level, or when ferromagnetic properties emerge in some materials as they are cooling down. Such phase transitions take place in matter because it is a network of particles, and as such, rules of network phase transition directly apply to it. Phase transitions in networks happen as links are added to a network, meaning that having N nodes, in each time increment, a link is placed between a randomly chosen pair of them. The transformation from a set of disconnected nodes to a fully connected network is called the evolution of a network. If we begin with a network having N totally disconnected nodes (number of links is zero), and start adding links between randomly selected pairs of nodes, the evolution of the network begins. For some time we will just create pairs of nodes. After a while some of these pairs will connect, forming little trees. As we continue adding more links to the network, there comes a point when a giant component emerges in the network as some of these isolated trees connect to each other. This is called the critical point. In our natural example, this point corresponds to temperatures where materials change their state. Further adding nodes to the system, the giant component becomes even larger, as more and more nodes get a link to an other node which is already part of the giant component. The other special moment in this transition is when the network becomes fully connected, that is, when all nodes belong to the one giant component, which is effectively the network itself at that point.〔 == Conditions for emergence of a giant component == Condition for the emergence of the giant component was predicted by Erdős and Renyi in their paper:〔Erdős P., Rényi A. On random graphs //Publicationes Mathematicae Debrecen. – 1959. – Т. 6. – С. 290-297〕 , where is the average degree of a random network. Thus, one link is sufficient for its emergence of the giant component. If expressing the condition in terms of , one obtain: (1) Whew is the number of nodes, is the probability of clustering. Therefore, the larger a network, the smaller is sufficient for the giant component. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Evolution of a random network」の詳細全文を読む スポンサード リンク
|